Kernel method

 ( Kernel Methods For Machine Learning ) 

In machine learning, kernel machines are a class of algorithms for pattern analysis, whose best known member is the support-vector machine (SVM). These methods involve using linear classifiers to solve nonlinear problems. The general task of pattern analysis is to find and study general types of relations (for example Cluster analysis, , principal components, , classifications) in datasets. For many algorithms that solve these tasks, the data in raw representation have to be explicitly transformed into feature vector representations via a user-specified feature map: in contrast, kernel methods require only a user-specified kernel, i.e., a similarity function over all pairs of data points computed using inner products. The feature map in kernel machines is infinite dimensional but only requires a finite dimensional matrix from user-input according to the representer theorem. Kernel machines are slow to compute for datasets larger than a couple of thousand examples without parallel processing.

Kernel methods owe their name to the use of kernel functions, which enable them to operate in a high-dimensional, implicit feature space without ever computing the coordinates of the data in that space, but rather by simply computing the between the images of all pairs of data in the feature space. This operation is often computationally cheaper than the explicit computation of the coordinates. This approach is called the " kernel trick".

Kernel functions have been introduced for sequence data, Graph kernel, text, images, as well as vectors.

Algorithms capable of operating with kernels include the kernel perceptron, support-vector machines (SVM), , principal components analysis (PCA), canonical correlation analysis, ridge regression, spectral clustering, Adaptive filter and many others.

Most kernel algorithms are based on convex optimization or eigenproblems and are statistically well-founded. Typically, their statistical properties are analyzed using statistical learning theory (for example, using Rademacher complexity).

---

Motivation and informal explanation Kernel methods can be thought of as instance-based learners: rather than learning some fixed set of parameters corresponding to the features of their inputs, they instead "remember" the $i$-th training example $(\backslash mathbf\{x\}\_i,\; y\_i)$ and learn for it a corresponding weight $w\_i$. Prediction for unlabeled inputs, i.e., those not in the training set, is treated by the application of a similarity function $k$, called a kernel, between the unlabeled input $\backslash mathbf\{x\text{'}\}$ and each of the training inputs $\backslash mathbf\{x\}\_i$. For instance, a kernelized binary classifier typically computes a weighted sum of similarities $$\backslash hat\{y\}\; =\; \backslash sgn\; \backslash sum\_\{i=1\}^n\; w\_i\; y\_i\; k(\backslash mathbf\{x\}\_i,\; \backslash mathbf\{x\text{'}\}),$$ where

• $\backslash hat\{y\}\; \backslash in\; \backslash \{-1,\; +1\backslash \}$ is the kernelized binary classifier's predicted label for the unlabeled input $\backslash mathbf\{x\text{'}\}$ whose hidden true label $y$ is of interest;
• $k\; \backslash colon\; \backslash mathcal\{X\}\; \backslash times\; \backslash mathcal\{X\}\; \backslash to\; \backslash mathbb\{R\}$ is the kernel function that measures similarity between any pair of inputs $\backslash mathbf\{x\},\; \backslash mathbf\{x\text{'}\}\; \backslash in\; \backslash mathcal\{X\}$;
• the sum ranges over the labeled examples $\backslash \{(\backslash mathbf\{x\}\_i,\; y\_i)\backslash \}\_\{i=1\}^n$ in the classifier's training set, with $y\_i\; \backslash in\; \backslash \{-1,\; +1\backslash \}$;
• the $w\_i\; \backslash in\; \backslash mathbb\{R\}$ are the weights for the training examples, as determined by the learning algorithm;
• the sign function $\backslash sgn$ determines whether the predicted classification $\backslash hat\{y\}$ comes out positive or negative.

Kernel classifiers were described as early as the 1960s, with the invention of the kernel perceptron. Cited in They rose to great prominence with the popularity of the support-vector machine (SVM) in the 1990s, when the SVM was found to be competitive with neural networks on tasks such as handwriting recognition.

---

Mathematics: the kernel trick The kernel trick avoids the explicit mapping that is needed to get linear learning algorithms to learn a nonlinear function or decision boundary. For all $\backslash mathbf\{x\}$ and $\backslash mathbf\{x\text{'}\}$ in the input space $\backslash mathcal\{X\}$, certain functions $k(\backslash mathbf\{x\},\; \backslash mathbf\{x\text{'}\})$ can be expressed as an inner product in another space $\backslash mathcal\{V\}$. The function $k\; \backslash colon\; \backslash mathcal\{X\}\; \backslash times\; \backslash mathcal\{X\}\; \backslash to\; \backslash mathbb\{R\}$ is often referred to as a kernel or a kernel function. The word "kernel" is used in mathematics to denote a weighting function for a weighted sum or integral.

Certain problems in machine learning have more structure than an arbitrary weighting function $k$. The computation is made much simpler if the kernel can be written in the form of a "feature map" $\backslash varphi\backslash colon\; \backslash mathcal\{X\}\; \backslash to\; \backslash mathcal\{V\}$ which satisfies $$k(\backslash mathbf\{x\},\; \backslash mathbf\{x\text{'}\})\; =\; \backslash langle\; \backslash varphi(\backslash mathbf\{x\}),\; \backslash varphi(\backslash mathbf\{x\text{'}\})\; \backslash rangle\_\backslash mathcal\{V\}.$$The key restriction is that $\backslash langle\; \backslash cdot,\; \backslash cdot\; \backslash rangle\_\backslash mathcal\{V\}$ must be a proper inner product. On the other hand, an explicit representation for $\backslash varphi$ is not necessary, as long as $\backslash mathcal\{V\}$ is an inner product space. The alternative follows from Mercer's theorem: an implicitly defined function $\backslash varphi$ exists whenever the space $\backslash mathcal\{X\}$ can be equipped with a suitable measure ensuring the function $k$ satisfies Mercer's condition.

Mercer's theorem is similar to a generalization of the result from linear algebra that associates an inner product to any positive-definite matrix. In fact, Mercer's condition can be reduced to this simpler case. If we choose as our measure the counting measure $\backslash mu(T)\; =\; |T|$ for all $T\; \backslash subset\; X$, which counts the number of points inside the set $T$, then the integral in Mercer's theorem reduces to a summation$$\backslash sum\_\{i=1\}^n\backslash sum\_\{j=1\}^n\; k(\backslash mathbf\{x\}\_i,\; \backslash mathbf\{x\}\_j)\; c\_i\; c\_j\; \backslash geq\; 0.$$If this summation holds for all finite sequences of points $(\backslash mathbf\{x\}\_1,\; \backslash dotsc,\; \backslash mathbf\{x\}\_n)$ in $\backslash mathcal\{X\}$ and all choices of $n$ real-valued coefficients $(c\_1,\; \backslash dots,\; c\_n)$ (cf. positive definite kernel), then the function $k$ satisfies Mercer's condition.

Some algorithms that depend on arbitrary relationships in the native space $\backslash mathcal\{X\}$ would, in fact, have a linear interpretation in a different setting: the range space of $\backslash varphi$. The linear interpretation gives us insight about the algorithm. Furthermore, there is often no need to compute $\backslash varphi$ directly during computation, as is the case with support-vector machines. Some cite this running time shortcut as the primary benefit. Researchers also use it to justify the meanings and properties of existing algorithms.

Theoretically, a Gram matrix $\backslash mathbf\{K\}\; \backslash in\; \backslash mathbb\{R\}^\{n\; \backslash times\; n\}$ with respect to $\backslash \{\backslash mathbf\{x\}\_1,\; \backslash dotsc,\; \backslash mathbf\{x\}\_n\backslash \}$ (sometimes also called a "kernel matrix"), where $K\_\{ij\}\; =\; k(\backslash mathbf\{x\}\_i,\; \backslash mathbf\{x\}\_j)$, must be positive semi-definite (PSD). Empirically, for machine learning heuristics, choices of a function $k$ that do not satisfy Mercer's condition may still perform reasonably if $k$ at least approximates the intuitive idea of similarity. Regardless of whether $k$ is a Mercer kernel, $k$ may still be referred to as a "kernel".

If the kernel function $k$ is also a covariance function as used in Gaussian processes, then the Gram matrix $\backslash mathbf\{K\}$ can also be called a covariance matrix.

---

Applications Application areas of kernel methods are diverse and include geostatistics, kriging, inverse distance weighting, 3D reconstruction, bioinformatics, cheminformatics, information extraction and handwriting recognition.

---

Popular kernels

• Fisher kernel
• Kernel smoother
• Polynomial kernel
• Radial basis function kernel (RBF)
• Neural tangent kernel
• Neural network Gaussian process (NNGP) kernel

---

See also

• Kernel methods for vector output
• Kernel density estimation
• Representer theorem
• Similarity learning
• Cover's theorem

---

Further reading

• (2025). 9780511809682, Cambridge University Press. ISBN 9780511809682
• (2025). 9781118211212, Wiley. . ISBN 9781118211212
• (2025). 9780262536578, MIT Press. . ISBN 9780262536578

---

External links

• Kernel-Machines Org—community website
• onlineprediction.net Kernel Methods Article

Post Comment